package com.rui.shangXueTang.kruskal;

/**
 * @author : [锐神NO.3]
 * @version : [v1.0]
 * @className : Dynamic
 * @createTime : [2022/2/19 15:51]
 * @description : [描述该类的功能]
 */

public class Dynamic {
    public static void main(String[] args) {
        int[][] arr = {
                {1,3,5,9},
                {8,1,3,4},
                {5,0,6,1},
                {8,8,4,0}
        };

        System.out.println(myanmic(arr));
    }

    public static int myanmic(int[][] arr){
        if(arr == null || arr.length == 0){
            return 0;
        }
        //声明一个新的二维数组，用来存储计算路劲的值
        int[][] dp = new int[arr.length][arr[0].length];
        dp[0][0] = arr[0][0];

        //从左边第一行开始计算路劲值
        for(int i = 1 ; i < dp[0].length ; i++){
            dp[0][i] = dp[0][i-1] + arr[0][i];
        }

        for(int i = 1 ; i < arr.length ; i++){
            for(int j = 0 ; j < dp[i].length ; j++){
                if(j == 0){
                    dp[i][j] = dp[i-1][j] + arr[i][j];
                }else if(dp[i-1][j] < dp[i][j-1]){
                    dp[i][j] = dp[i-1][j] + arr[i][j];
                }else {
                    dp[i][j] = dp[i][j-1] + arr[i][j];
                }
            }
        }
        return dp[dp.length -1][dp[dp.length - 1].length - 1];
    }
}
